package com.shm.leetcode;

/**
 * 练习：编辑距离 II
 * 给你两个单词 s 和 t，请你计算出将 s 转换成 t 所使用的最少操作数。
 *
 * 你可以对一个单词进行如下两种操作：
 *
 * 删除一个字符
 * 替换一个字符
 * 注意：
 *
 * 不允许插入操作
 * 题目保证有解
 * 示例：
 *
 *
 * 输入：s = "abcdefg", t = "abdde"
 * 输出：3
 * 提示：
 *
 * 1 <= len(s), len(t) <= 200
 *
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/high-frequency-algorithm-exercise/omxcgt/
 * @author SHM
 */
public class MinDistanceII {
    /**
     * 删除的时候是有条件限制的，因为不能插入，所以删除的时候必须保证删除s的一个字符i后，必须保证剩下的i-1个字符个数必须大于等于t的前j个字符才能和t匹配，如果小于肯定无法匹配，因为s[0:i-1]太短了~~~~
     *
     * 作者：mt19937
     * 链接：https://leetcode-cn.com/leetbook/read/high-frequency-algorithm-exercise/omxcgt/?discussion=NGzIPW
     * @param s
     * @param t
     * @return
     */
        public int edit_distance(String s, String t) {
            int n = s.length();
            int m = t.length();
            if(n*m==0){
                return n+m;
            }
            int[][] dp = new int[n+1][m+1];
            for(int i=0;i<=n;i++){
                dp[i][0]=i;
            }

            for(int j=0;j<=m;j++){
                dp[0][j]=j;
            }

            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++){
                    if(s.charAt(i-1)==t.charAt(j-1)){
                        dp[i][j]=dp[i-1][j-1];
                    }else{
                        if(i-1>=j){
                            dp[i][j]=Math.min(dp[i-1][j]+1,dp[i-1][j-1]+1);
                        }else{
                            dp[i][j]=dp[i-1][j-1]+1;
                        }
                    }
                }
            }

            return dp[n][m];
        }
}
